# 描述
# 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

# 输入描述：
# 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表
# 返回值描述：
# 返回链表的环的入口结点即可。而我们后台程序会打印这个节点
# 示例1
# 输入：
# {1,2},{3,4,5}
# 返回值：
# 3
# 说明：
# 返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3    

#记录已经走过的节点，如果下一个节点再走过的节点中，则为环入口
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        addr = []
        while pHead.next != None:    # 遍历
            addr.append(pHead)        # 记录地址到列表
            pHead = pHead.next        # 遍历下一个
            if pHead.next in addr:    # 存在下一个链表地址在列表中，则下一个链表就是入口
                return pHead.next
        return None                   # 无法循环，返回空